Cryptography is the discipline which embodies principles, means, and methods for the transformation of data in order to hide its information content, prevent its undetected modification and/or prevent its unauthorized use. Keys are utilized in many forms of cryptography. A key is a sequence of symbols that controls the operation of a cryptographic transformation (e.g. encipherment, decipherment, cryptographic check function computation, signature generation, or signature verification).
Public-key cryptography, also known as asymmetric cryptography, is a form of cryptography in which a user has a pair of cryptographic keys—a public key and a private key. The private key is kept secret, while the public key may be widely accessible to the public. The keys are related mathematically, but the private key cannot be practically derived from the public key. A message encrypted with the public key can be decrypted only with the corresponding private key. Applications of public key cryptography include public key encryption and digital signatures. In public key encryption, to ensure confidentiality, a message encrypted with a recipient's public key cannot be decrypted by anyone except the recipient possessing the corresponding private key. A digital signature refers to a message signed with a sender's private key to ensure authenticity or “authenticate” the sender. The signed message can be verified by anyone who has access to the sender's public key thereby proving that the sender signed it and that the message has not been tampered with.
One issue with public-key cryptography is proving that a public key is authentic, and has not been tampered with or replaced by a malicious third party. To address this issue, modern cryptography and network security systems often employ certificate-based authentication mechanisms to verify that a public key belongs to a particular user. Such certificate-based authentication mechanisms are usually implemented as a public key infrastructure (PKI), in which one or more third parties, known as certificate or certification authorities (CAs), certify ownership of key pairs. A CA issues public key certificates, updates expired public key certificates, and creates, manages and distributes a certificate revocation list that repudiates unscrupulous users. The CA also generates public and private keys as needed. The public key certificates generated and issued by the CA are signed with a digital signature of the CA. A certificate signed by the issuer CA proves that the issuer CA trusts the subject that certificate is issued to. Any entity that trusts the CA can then assume that a public key in a given certificate is valid and is associated with the entity specified in that certificate.
The ITU Telecommunication Standardization Sector (ITU-T) is based in Geneva, Switzerland and coordinates standards for telecommunications on behalf of the International Telecommunication Union (ITU). X.509 is an ITU-T standard for public key infrastructure (PKI). The X.509 working group (PKIX) is a working group of the Internet Engineering Task Force (IETF) dedicated to creating Request for Comments (RFCs) and other standards documentation on issues related to public key infrastructure based on X.509 certificates. For example, a version of the X.509 standard is version 3 (X.509v3). All of the X.509 standards referred to herein are incorporated by reference herein in their entirety, and may be obtained at www.itu.int/rec/T-REC-X.509/en. X.509 specifies, among other things, standard formats for public key certificates and a certification path validation algorithm.
Path validation is a process whereby a path processing module in a device of a relying party takes a signed object, which may be a certificate, and traces its trust in the signature of that object back to one of the device's trust anchors (i.e., known trusted public keys) to verify that a given certificate “path” is valid under a given PKI. As used herein the terms “path” and “certificate path” refer to a sequence of a number (N) of certificates that starts with the subject certificate and proceeds through a number of intermediate certificates up to a trusted root certificate, issued by the trust anchor which is typically a trusted Certification Authority (CA). Path validation is necessary for a relying party to make an informed trust decision when presented with any certificate that is not already explicitly trusted. Section 6 of Request for Comments (RFC) 3280, “Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile”, Housley, et. al., April 2002, defines a standardized path validation algorithm for X.509 certificates. Request for Comments (RFC) 3280 is incorporated by reference herein in its entirety. A copy of RFC 3280 may be obtained at http://www.ietf.org/rfc/rfc3280.txt. Path validation performed by a path processing module is complex and includes, among other things, determinations that certificates along the path meet name constraints, path length constraints, and policy constraints imposed by any certificate closer to the trust anchor along the path. Some aspects of the path validation algorithm specified in RFC 3280 will now be described with reference to FIG. 1.
FIG. 1 illustrates a flow chart of a method for path validation 100 with respect to a particular X.509 certificate in a chain of X.509 certificates. The method for path validation 100 can be performed by a path processing module implemented on a computer of a relying party that is attempting to validate an X.509 certificate through a chain of X.509 certificates.
Path validation 100 begins at step 110 where the path processing module receives input information as described in section 6.1.1 of RFC 3280. The input information received by the path processing module can include certificate path or “chain” to be evaluated (i.e., a prospective certification path of length N); the current date/time; a list of certificate policy object identifiers (OIDs) or “user-initial-policy-set” acceptable to the relying party (or any); trust anchor information about the trust anchor of the certificate path describing the CA that serves as the trust anchor for the certification path; and indicators regarding whether policy mapping is allowed and how/when/whether the “any” policy OID is to be tolerated. The list of certificate policy OIDs is a set of certificate policy identifiers naming the policies that are acceptable to the certificate user. The user-initial-policy-set contains a special value “any-policy” if the user is not concerned about certificate policy. The trust anchor information includes: (1) the trusted issuer name, (2) the trusted public key algorithm, (3) the trusted public key, and (4) optionally, the trusted public key parameters associated with the public key. The trust anchor information may be provided to the path processing module in the form of a self-signed certificate. The trusted anchor information is trusted because it was delivered to the path processing module by some trustworthy out-of-band procedure. If the trusted public key algorithm requires parameters, then the parameters are provided along with the trusted public key. The indicators regarding whether policy mapping is allowed can include: an initial-policy-mapping-inhibit indicator, which indicates if policy mapping is allowed in the certification path, an initial-explicit-policy indicator, which indicates if the path must be valid for at least one of the certificate policies in the user-initial-policy-set, and an initial-any-policy-inhibit indicator, which indicates whether the any-Policy OID should be processed if it is included in a certificate.
At step 120, the path processing module performs an initialization phase to establish state variables based upon the inputs provided at step 110. The state variables established during the initialization phase are described in section 6.1.2 of RFC 3280, and will not be described in detail here. One of the state variables that is generated is a maximum path length. The maximum path length is an integer initialized to a value “N”, and is decremented (“N−1”) for each non-self-issued certificate in the path, and may be reduced to a value in a path length constraint field specified within the basic constraints extension of a CA certificate. To explain further, a public key certificate includes a number of fields that are specified in the X.509 standards. One of these fields is a “path length constraint” field that is used to specify whether the public key subject to certification is to be used for signature by the certificate authority (CA) or by the user. The path length constraint (PLC) informs relying parties who trust a particular certification authority to only trust certificates that are signed by another CA if the other CA is within a particular path length (or number of CA hops) from the certification authority of the relying party.
At steps 130 through 170, the path processing module processes each certificate in the path, starting from the trust anchor. Each certificate is the path is individually processed at step 130 by performing a number of checks with respect to that certificate. These “checks” will be briefly summarized below, and more details are provided in section 6.1.3 of RFC 3280. Some or all of these checks can be performed depending on the particular implementation. In addition, the checks described below do not necessarily need to be performed in the particular order listed. Although not illustrated in FIG. 1, if any certificate in the path fails one of the checks performed during processing at step 130, the method for path validation 100 terminates and path validation fails.
At step 130, the path processing module processes the next certificate as in the path. (The first iteration of step 130 begins by processing the certificate of the trust anchor, and then continues for each certificate in the path as indicated by steps 140 and 150.) The certificate processing performed by the path processing module will now be briefly summarized; however, a more detailed explanation is provided in section 6.1.3 of RFC 3280. For each certificate, the path processing module checks: (1) the public key algorithm and parameters; (2) the current date/time against the validity period of the certificate; (3) revocation status to ensure the certificate is not revoked (e.g., by a certificate revocation list (CRL), online certificate status protocol (OCSP), or some other mechanism); (4) the issuer name to ensure that it equals the subject name of the previous certificate in the path; (5) name constraints to make sure the subject name is within the permitted subtrees list of all previous CA certificates and not within the excluded subtrees list of any previous CA certificate; (6) the asserted certificate policy OIDs against the permissible OIDs as of the previous certificate, including any policy mapping equivalencies asserted by the previous certificate; (7) policy constraints and basic constraints to ensure that any explicit policy requirements are not violated and that the certificate is a CA certificate, respectively; (8) the path length to ensure that it does not exceed any maximum path length asserted in this or a previous certificate; (9) the key usage extension to ensure that is allowed to sign certificates; and (10) any other critical extensions the certificate contains.
At step 140, the path processing module determines if the certificate is the last certificate in the path. If the certificate is the last certificate in the path, with no name constraint or policy violations or any other error condition, the method for path validation 100 proceeds to step 160, where the path processing module performs “wrap up” processing as described in section 6.1.5 of RFC 3280, and the certificate path validation method terminates successfully at step 170.
If the path processing module determines that the certificate is not the last certificate in the path, then the method for path validation 100 proceeds to step 150, where the path processing module performs processing to prepare for the next certificate as described in section 6.1.4 of RFC 3280. Among the many steps performed by the path processing module at step 150 to prepare for the next certificate, the path processing module verifies that the maximum path length (max_path_length) is greater than zero and decrements the maximum path length (max_path_length) by 1 if the certificate was not self-issued. If a path length constraint (pathLengthConstraint) is present in the certificate and is less than the maximum path length (max_path_length), the path processing module sets the maximum path length (max_path_length) to the value of the path length constraint (pathLengthConstraint).
Although the use a maximum path length constraint works well in many PKI systems, in certain scenarios using a maximum path length constraint may be inadequate or problematic.
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.
The apparatus and method components have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiments of the present invention so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art having the benefit of the description herein.